package com.mergeSort;

import com.Sort;

/**
 * @author 罗俊华
 * @date 2021/5/11 - 2:13 下午
 * 归并排序
 */
public class MergeSort<Item extends Comparable<Item>> extends Sort<Item> {


    @Override
    public void sort(Item[] comparableArray) {

        int step = 1;
        while (step <= comparableArray.length / 2) {
            for (int low = 0; low < comparableArray.length - step; low++) {
                merge(comparableArray, low, low + step);

            }
            step++;
        }


    }


    public void merge(Item[] comparableArray, int low, int high) {
        if (low == high) {
            return;
        }
//          辅助数组
        Object[] aux = /*(Item[])*/ new Object[(high + low) / 2 + 1];
        int mid = (low + high) / 2;
        for (int i = 0; i < aux.length; i++) {
            if (low <= mid && super.less(comparableArray[low], comparableArray[high])) {
                aux[i] = comparableArray[low];
                low++;
            } else if (high > mid) {
                aux[i] = comparableArray[high];
                high--;
            }
        }
        System.arraycopy(aux, 0, comparableArray, low, high - low);

    }
}
